This invention relates to a dispatch mechanism and to a router or sender station for dispatching data units comprising one or more fragments via a telecommunications network.
The invention finds particular application to transmission of data units via an inter- or intra-network operating under an Internet Protocol.
FIG. 1 is a schematic representation of an instance of an inter- or intra-net with a router 10 being provided in the path between a source 12 and a destination 14. Between the source 12 (or sender node) and the router node 10, a net 16 is shown and between the router node 10 and the destination node 14 a further net 18 is shown. In practice, the net 16 and the net 18 can be one and the same and the router 10 effectively forms a "staging post" between the source 12 and the destination 14. In the following, reference is made to a dispatch mechanism. It should be appreciated that the dispatch mechanism could, in the present context, equally form part of the source, or sender station 12 or the router station 10.
FIG. 2 is a schematic representation of the configuration of a station for a router 10 or source or destination 12, 14. These stations can be implemented using any appropriate technology. However, as illustrated in FIG. 2, the station 10 is implemented by a server computer 20 comprising a system unit 22, optionally with a display 38, keyboard 40 and other input devices 42. It should be noted that the router 10 need not include a keyboard, display, etc. FIG. 2A is a schematic block representation of aspects of the contents of the system unit 22. As illustrated in FIG. 2A, the system unit includes a processor 28, memory 30, disk drives 24 and 26, and a communications adaptor 32 for connection to one or more telecommunications lines 34 for connection to the telecommunications network 16/18. As illustrated in FIG. 2A, the components of the system unit are connected via a bus arrangement 36. It will be appreciated that FIGS. 2/2A are a general schematic representation of one possible configuration for a server computer for forming a router or sender or destination station, and that many alternative configurations could be provided.
Conceptually, the Internet provides three sets of services. At the lowest level, a connectionless delivery system provides a foundation on which everything rests. At the next level, a reliable transport service provides a high level platform. At the third level, application services are provided which rely on the reliable transport service.
A fundamental Internet service consists of an unreliable, best-effort, connectionless, packet delivery system. The service is described as being "unreliable" because delivery is not guaranteed. A packet may be lost, duplicated, or delivered out of order, but the Internet will not detect such conditions, nor will it inform the sender or receiver. The service is described as being "connectionless" because each packet is treated independently from all others. A sequence of packets sent from one machine to another may travel over different paths, or some may be lost while others are delivered. The service may be described as "best-effort" because the Internet aims to deliver packets.
The protocol that defines the unreliable, connectionless, delivery mechanism is called the "Internet Protocol", and is usually referred to by its initials IP. IP defines the formal specification of data formats, including a basic unit of data transfer and the exact format of all data passing across the Internet. IP also includes rules which specify how packets should be processed and how errors should be handled. In particular, IP embodies the idea of unreliable delivery and packet routing.
Further details of aspects of the Internet and TCP/IP protocols may be found, for example, in the following U.S. Pat. Nos.: 5,293,379; 5,307,347; 5,307,413; 5,309,437; 5,351,237; and 5,535,199.
The basic unit of data transfer over the Internet is termed an "Internet datagram", or alternative "IP datagram", or simply "datagram". A datagram comprises header and data areas, and source and destination addresses. There is no fixed size for a datagram. Bearing this in mind, and also the physical constraints of the underlying hardware services on which the Internet is based, it is necessary to divide the datagram into portions called "fragments".
FIG. 3 illustrates the format of an Internet datagram. The same format is used for a fragment of a datagram.
The 4 bit version field (VERS) specifies the IP protocol version and is used to ensure that all of the nodes along the path of the datagram agree on the format.
The LEN field gives the datagram header length measured in 32 bit words. The TOTAL LENGTH field gives the length of the IP datagram measured in octets including the length of the header and data.
The SERVICE TYPE field contains handling details for the datagram.
Three fields in the datagram header, IDENT, FLAGS, and FRAGMENT OFFSET, control fragmentation and reassembly of datagrams. The field IDENT contains a unique identifier that identifies the datagram.
In the FLAGS field, a first bit specifies whether the datagram may be fragmented, and a second bit indicates whether this is the last fragment in the datagram. The FRAGMENT OFFSET field specifies the offset of this fragment in the original datagram, measured in units of 8 octets, starting at offset zero.
As each fragment has the same basic header format as a complete datagram, the combination of the FLAGS and FRAGMENT OFFSET fields are used to indicate that the headers relate to fragments, and to indicate the position of the fragment within the original datagram. The FRAGMENT OFFSET field identifies the position within the datagram, and the second of the FLAGS bits mentioned above (which is sometimes called the MORE FRAGMENTS flag) is used to indicate whether there are any more fragments in the datagram, or conversely that the fragment concerned is the last fragment of the datagram.
The field PROTO is a form of type field. The HEADER CHECK SUM figure ensures integrity of header values.
SOURCE IP ADDRESS and DESTINATION IP ADDRESS contain 32 bit Internet addresses of the datagram's sender and intended recipient. The OPTIONS field and the PADDING field are optional in the datagram. The field labelled DATA represents the beginning of the data field.
FIG. 4 is a schematic representation of an output buffer, or queue 50 in which packets P1, P2, P3, etc., are stored for transmission at 58 to the network 18. The packets need to be queued before transmission in order to ensure that the network 18 may be accessed for transmission of the packet.
As shown in FIG. 4, the queue 50 has five equally sized queue locations. It should be noted that FIG. 4 is purely schematic for illustrative purposes only and in practice the output queue of, for example, a router 10 would typically have a much larger capacity, and would also not be limited to fixed sized packets. However, for the purposes of illustration, a new packet P4 is assumed to be ready to be inserted in the queue for transmission. In this case, there are still two free locations 56 and accordingly the new packet P4, 52, can be inserted in the queue at that position. In time, more locations within the queue win become free as individual packets are transmitted at 58.
However, FIG. 5 illustrates a situation where, for example due to traffic loading, it is not possible to output packets rapidly enough at 58 from the queue 50 so that the queue 50 becomes full. Accordingly, as illustrated in FIG. 5, when a new packet P6, 53, is ready to be inserted in the queue, there is no place for it. Although the Internet does not discard packets unnecessarily, in the situation as illustrated in FIG. 5, the typical approach to dealing with such an overload situation is to simply discard the packet 53. This is an illustration of why the Internet is described as an "unreliable" service, as no guarantee is given that a packet will arrive at its intended destination.
The present invention does not attempt to provide a complete solution to the loss of packets. However, the invention is intended to address a particular problem where the packets relate to fragments of a datagram.
FIG. 6 illustrates three datagrams D1, D2 and D3 which are to be transmitted from a router 10 via a given path. Datagram D1 comprises four fragments F1, F2, F3 and F4. Datagram D2 also comprises four fragments, F1, F2, F3 and F4. Datagram D3 comprises two data fragments F1 and F2.
FIG. 6A illustrates a situation where all of the fragments of datagram D1 have been queued in the queue 50 ready for transmission at 58. It will be noted (as is typically the case), that the fragments in the queue are not in the order intended for the datagram. Thus, fragment D1F1 is followed by fragment D1F2, then fragment D1F4 and finally fragment D1F3. By use of the TOTAL LENGTH, FRAGMENT OFFSET, and MORE FRAGMENTS fields of the fragment headers it is possible for the router 10 and/or for the final destination to determine whether the complete datagram has been sent and received, respectively.
FIG. 6A also shows that one fragment D2F1 of datagram D2 has already been queued in the queue 50. It also shows that two new fragments 60 and 62 need to be added to the queue in the queue 50. However, it is assumed that at the instant that it is intended to add the fragments 60 and 62, the queue 50 is full. In this case, it would traditionally be the case that fragment 60 would be discarded and similarly fragment 62 would be discarded as there is no room. The result of discarding fragment 62 is that the available band width has been used unnecessarily for transmission of fragment D2F1 of datagram D2 as the complete datagram will now not be sent. With regard to the datagram D3, if at a subsequent time when the queue is not full, the fragment D3F2 is available for placement in the queue 50, then the fragment D3F2 will be sent, which will also have the result of making inefficient use of the available bandwidth as the fragment F1 of datagram D3 was not sent.
Accordingly, an object of the present invention is to seek to mitigate the problems of the prior art approach to the transmission of data units (for example datagrams) comprising multiple fragments.